package Hot100.BackTracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class combinationSum3 {
    public static void main(String[] args) {
        System.out.println(new combinationSum3().combinationSum3(4,18));
    }
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        backTrack(k,n,1,0);
        return result;
    }
    public void backTrack(int k, int n, int startIndex, int num){
        if(path.size() == k){
            if(num == n){
                result.add(new ArrayList<>(path));
                return;
            }else {
                return;
            }
        }
        for (int i = startIndex; i <= Math.min(n - num,9); i++) {
            path.add(i);
            num += i;
            backTrack(k,n,i + 1,num);
            num -= i;
            path.removeLast();
        }
    }
}
